package graphPath;

import java.text.DecimalFormat;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

import org.jgrapht.WeightedGraph;
import org.jgrapht.alg.util.UnionFind;
import org.jgrapht.graph.DefaultWeightedEdge;

public class MinimumSpanningTree {
	private double totalweight;
	

	
	
	public List <DefaultWeightedEdge> mst(final WeightedGraph <String, DefaultWeightedEdge> graph ){
		List<DefaultWeightedEdge> edges = new ArrayList<DefaultWeightedEdge>(graph.edgeSet());
		UnionFind<String> circle = new UnionFind <String>(graph.vertexSet());
		
		
		
		//sort the edges by their weight
		Collections.sort(edges, new Comparator<DefaultWeightedEdge>() {
			public int compare(DefaultWeightedEdge e1, DefaultWeightedEdge e2){
				
				return Double.valueOf(graph.getEdgeWeight(e1)).
						compareTo(Double.valueOf(graph.getEdgeWeight(e2)));
				
			}
			
			
		});
		
		totalweight=0;
		
		List<DefaultWeightedEdge> mst_edges = new ArrayList<DefaultWeightedEdge>();
//		List <Object> result = new ArrayList<Object>();
		List<Double> weight = new ArrayList<Double>();
		List<String> vertex = new ArrayList<String>();
		
		
		//add the edge and decide whether it forms circle
		for(DefaultWeightedEdge element : edges){
			String v_source = graph.getEdgeSource(element);
			String v_target = graph.getEdgeTarget(element);
			
			if(circle.find(v_source).equals(circle.find(v_target))){
				continue;
			}
			
			
			circle.union(v_source, v_target);
			
			
			
			mst_edges.add(element);

			
			totalweight=totalweight+graph.getEdgeWeight(element);
//			result.add(element);
//			result.add(graph.getEdgeWeight(element));
			weight.add(graph.getEdgeWeight(element));
			
			if(!vertex.contains(graph.getEdgeSource(element))){
				
				vertex.add(graph.getEdgeSource(element));
				
			}
			
			if(!vertex.contains(graph.getEdgeTarget(element))){
				vertex.add(graph.getEdgeTarget(element));
			}
			
			
			
		}
		
		
		
		
		
		
		System.out.println("Minimum Spanning Tree:  " );
		
		System.out.println("V = " + vertex);
		System.out.println("E = " + mst_edges);
		System.out.println("Weight = " + weight);
		return mst_edges;
		
		
		
	}
	

	public double getTotal(){
		DecimalFormat f = new DecimalFormat("######.00");
		
		
		System.out.println("Total Weight:"+ f.format(totalweight));
		
		
		return totalweight;
	}
	
	
	
	
	
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
